// https://leetcode-cn.com/problems/merge-two-sorted-lists/

// 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

#include <vector>
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
	ListNode* mergeTwoLists1(ListNode* list1, ListNode* list2) {
		ListNode * head = new ListNode(0);
		ListNode * index = head;
		
		while(list1 && list2){
			if(list1->val <= list2->val){
				index->next = list1;
				list1 = list1->next;
			}else{
				index->next = list2;
				list2 = list2->next;
			}
			index = index->next;
		}
		
		if(list1){
			index->next = list1;
		}
		if(list2){
			index->next = list2;
		}
		head = head->next;
		return head;
	}

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
		if(!list1){
			return list2;
		}else if(!list2){
			return list1;
		}
		ListNode* head = nullptr;
		ListNode* index = nullptr;
		int i = 0;
		while(list1 && list2){
			ListNode* tmp = new ListNode;
			tmp->next= nullptr;
			
			if(list1->val <= list2->val){
				tmp->val = list1->val;
				list1 = list1->next;
			}else{
				tmp->val = list2->val;
				list2 = list2->next;
			}
			
			if(i == 0){
				head = tmp;
				index = tmp;
			}else{
				index->next = tmp;
				index = index->next;
			}
			i++;
		}
		if(list1){
			index->next = list1;
		}else{
			index->next = list2;
		}
		
		return head;
    }
	
	ListNode * init(vector<int> nums){
		int len = nums.size();
		if(len == 0){
			return nullptr;
		}
		
		ListNode * head = new ListNode;
		head->val = nums[0];
		head->next = nullptr;
		if(len == 1){
			return head;
		}
		ListNode * index = head;
		for(int i = 1; i < len; i++){
			ListNode * tmp = new ListNode;
			tmp->val = nums[i];
			tmp->next = nullptr;
			index->next = tmp;
			index = tmp;
		}
		return head;
	}

	void show(ListNode * head){
		while(head){
			cout << head->val << " ";
			head = head->next;
		}
		cout << endl;
	}
};



int main(){
	Solution so;
	vector<int> n1 = {1,3,5};
	vector<int> n2 = {3,5,6};
	ListNode * h1 = so.init(n1);
	ListNode * h2 = so.init(n2);
	so.show(h1);
	so.show(h2);
	ListNode * newHead = so.mergeTwoLists1(h1, h2);
	so.show(newHead);
	return 0;
}